package main

import (
	"fmt"
)

func GetNext(s string) (next []int) {
	next = make([]int, len(s))
	next[0] = -1
	y := 0
	l := -1

	for y < len(s)-1 {
		if l == -1 || s[l] == s[y] {
			l++
			y++

			if s[y] != s[l] {
				next[y] = l
			} else {
				next[y] = next[l]
			}

		} else {
			l = next[l]
		}
	}

	return next

}

func IndexKMP(s string, t string) int {
	next := GetNext(t)
	i := 0 //S
	j := 0 //T

	for i < len(s) && j < len(t) {
		if j == -1 || s[i] == t[j] {
			i++
			j++
		} else {
			j = next[j]
		}
	}

	if j == len(t) { //完成
		return i - j
	} else {
		return -1
	}

}

func main() {
	a := "aabbababa"
	b := "baba"

	fmt.Println(IndexKMP(a, b))
}
